Ana içeriğe geç

Kuyruk (queue) Veri Yapısı

Kuyruk (queue) veri yapısı, elemanların sonuna ekleme (enqueue) ve başından çıkarma (dequeue) işlemlerinin yapılabildiği, ilk giren ilk çıkar (FIFO - first in, first out) prensibine göre çalışan bir veri yapısıdır.

Kuyruk, gerçek hayattaki birçok senaryoya benzer şekilde kullanılabilir. Örneğin bir restoranda sipariş veren müşterilerin sırasını tutmak, bir yolcu otobüsünde binen yolcuların sırasını belirlemek, bir e-posta sunucusunda gönderilen e-postaların sırasını belirlemek gibi durumlarda kullanılabilir.

Kuyruk veri yapısı genellikle linked list veya array gibi başka veri yapıları üzerine inşa edilir. En önemli özelliklerinden biri, veri yapısının ilk elemanı ile son elemanı arasındaki mesafenin sabit olmasıdır.

Kuyrukların diğer kullanımları arasında işlem sırasının kontrolü, işlemciler arasında veri iletimi, çeşitli arama algoritmalarında kullanım gibi uygulamalar yer alabilir.

Kuyruk (Queue) Veri Yapısı Uygulamaları​

Kuyruk veri yapısı, birçok bilgisayar bilimi uygulamasında kullanılmaktadır. İşte bazı örnekler:

  1. İşlemci planlaması: İşlemci planlaması, kuyruk veri yapısının en yaygın uygulamalarından biridir. İşlemci, bir dizi işlemi sırayla işlemek zorunda olduğu için, işlemlerin beklemek üzere sıraya alındığı bir kuyruk kullanılır.
  2. Ağ yönetimi: Ağ yönetiminde, kuyruk veri yapısı, bir ağdaki veri paketlerinin yönetimi için kullanılır. Paketler, kuyruğa eklenir ve sırayla işlenir.
  3. Kaynak tahsisi: Kaynak tahsisi, kuyruk veri yapısının bir başka önemli uygulamasıdır. Örneğin, bir dosya sunucusu, birden çok kullanıcının dosya isteklerini işlemek zorunda olduğunda, dosya istekleri kuyruğa eklenir ve sırayla işlenir.
  4. Bellek yönetimi: Bellek yönetiminde, kuyruk veri yapısı, bellek bloklarının ayrılması ve tahsis edilmesi için kullanılır. Bellek blokları, kuyruğa eklenir ve sırayla işlenir.
  5. Sıralama: Sıralama algoritmaları, kuyruk veri yapısını kullanarak gerçekleştirilebilir. Örneğin, bir dizi elemanın sıralanması için kuyruk tabanlı bir sıralama algoritması kullanılabilir.

Bu uygulamaların yanı sıra, kuyruk veri yapısı, birçok farklı alanda kullanılabilir. Örneğin, oyun geliştirme, veritabanı yönetimi, simülasyonlar ve grafik işleme gibi alanlarda da kullanılabilir.

Diziler ile Queue İşlemleri​

Diziler ile kuyruk, C programlama dilinde kolayca oluşturulabilir. Temel olarak, bir dizi kullanarak kuyruk oluşturulur ve kuyruk işlemleri (enqueue, dequeue, peek vb.) dizinin indeksleri üzerinde gerçekleştirilir.

İşte bir örnek C kodu, diziler ile kuyruğun enqueue (kuyruğa ekleme) ve dequeue (kuyruktan çıkarma) işlemlerini gerçekleştirir:

#include <stdio.h>
#define MAXSIZE 10

int queue[MAXSIZE];
int rear = -1;
int front = -1;

void enqueue(int item) {
  if (rear == MAXSIZE - 1) {
    printf("Queue is full");
  } else {
    if (front == -1) {
      front = 0;
    }
    rear++;
    queue[rear] = item;
    printf("Enqueued %d to queue\n", item);
  }
}

int dequeue() {
  int item;
  if (front == -1 || front > rear) {
    printf("Queue is empty\n");
    return -1;
  } else {
    item = queue[front];
    front++;
    printf("Dequeued %d from queue\n", item);
    return item;
  }
}

int main() {
  enqueue(1);
  enqueue(2);
  enqueue(3);
  enqueue(4);
  enqueue(5);

  dequeue();
  dequeue();
  dequeue();

  return 0;
}

Bu kodda, queue isimli bir dizi oluşturulur ve rear ve front adında iki işaretçi tanımlanır. rear, kuyruğun son elemanını işaret ederken, front, kuyruğun ilk elemanını işaret eder. enqueue fonksiyonu, kuyruğa eleman eklerken, dequeue fonksiyonu, kuyruktan eleman çıkarır.

Bağlı Listeler ile Queue İşlemleri​

Bağlı listeler ve kuyruklar, bir veri yapısı olarak birbirleriyle yakından ilişkilidir. Kuyruk, ilk giren ilk çıkar (FIFO) prensibine dayalı bir veri yapısıdır. Bu, bir kuyruğa öğe eklendiğinde, yeni öğenin kuyruğun sonuna eklenmesi ve kuyruğun başındaki öğenin kuyruktan çıkarılması gerektiği anlamına gelir.

Bağlı listeler, öğeleri sıralı olarak depolamak için kullanılan bir veri yapısıdır. Her bir öğe, kendisinden sonra gelen öğenin adresini tutar ve son öğenin adresi null değerini alır. Bu sayede, bir bağlı listenin başlangıç noktasından başlayarak öğeleri sırayla takip edilebilir.

Bir kuyruğu uygulamak için, genellikle bir bağlı liste kullanılır. Bu, yeni öğelerin kuyruğun sonuna eklenmesi ve kuyruktan çıkarılacak öğelerin kuyruğun başından alınması için uygun bir yapıdır.

Bağlı listenin sonuna yeni bir öğe eklemek, kuyruğa yeni bir öğe eklemekle aynıdır. Bu işlem, bağlı listenin sonundaki null değerli öğeyi yeni öğenin adresiyle değiştirerek gerçekleştirilebilir. Kuyruktan bir öğe çıkarmak, bağlı listenin başındaki öğeyi kuyruktan çıkararak gerçekleştirilebilir.

Kuyruk işlemleri şunları içerir:

  • enqueue(item): Kuyruğun sonuna yeni bir öğe ekler.
  • dequeue(): Kuyruğun başındaki öğeyi kuyruktan çıkarır ve döndürür.
  • peek(): Kuyruğun başındaki öğeyi döndürür, ancak kuyruktan çıkarmaz.
  • isEmpty(): Kuyruğun boş olup olmadığını kontrol eder.
  • size(): Kuyruktaki öğe sayısını döndürür.

Bu işlemler, bağlı listelerin kullanıldığı kuyruk uygulamaları için temel işlemlerdir. Bağlı listeler, kuyruklar gibi diğer veri yapıları için de kullanılabilir ve farklı işlemler sağlayabilir.

Aşağıda, bağlı listeleri kullanarak bir kuyruk veri yapısını uygulayan bir C kodu örneği verilmiştir:

#include <stdio.h>
#include <stdlib.h>

// Kuyruk elemanlarını temsil eden bağlı liste düğümü
struct Node {
    int data;
    struct Node* next;
};

// Kuyruk yapısını temsil eden struct
struct Queue {
    struct Node *front, *rear;
};

// Yeni bir düğüm oluşturup geri döndüren yardımcı fonksiyon
struct Node* newNode(int data) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// Yeni bir kuyruk oluşturup geri döndüren fonksiyon
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}

// Kuyruğa yeni bir eleman ekleyen fonksiyon
void enqueue(struct Queue* q, int data) {
    struct Node* temp = newNode(data);
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

// Kuyruktan bir eleman çıkaran fonksiyon
void dequeue(struct Queue* q) {
    if (q->front == NULL) {
        printf("Kuyruk bos!\n");
        return;
    }
    struct Node* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL)
        q->rear = NULL;
    free(temp);
}

// Kuyruğun başındaki elemanı döndüren fonksiyon
int peek(struct Queue* q) {
    if (q->front == NULL) {
        printf("Kuyruk bos!\n");
        return -1;
    }
    return q->front->data;
}

// Kuyruğun boş olup olmadığını kontrol eden fonksiyon
int isEmpty(struct Queue* q) {
    return (q->front == NULL);
}

// Kuyruktaki eleman sayısını döndüren fonksiyon
int size(struct Queue* q) {
    struct Node* temp = q->front;
    int count = 0;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

// Ana fonksiyon
int main() {
    struct Queue* q = createQueue();

    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    enqueue(q, 40);

    printf("Kuyruktaki elemanlar: ");
    while (!isEmpty(q)) {
        printf("%d ", peek(q));
        dequeue(q);
    }

    printf("\n");

    return 0;
}


Bu kod, bir kuyruk oluşturmak için createQueue() fonksiyonunu kullanır. Kuyruğa eleman eklemek için enqueue() fonksiyonunu, kuyruktan eleman çıkarmak için dequeue() fonksiyonunu kullanır. peek() fonksiyonu, kuyruğun başındaki elemanı döndürür, ancak kuyrukta herhangi bir değişiklik yapmaz. isEmpty() fonksiyonu, kuyruğun boş olup olmadığını kontrol eder. Kuyruk boşsa 1, doluysa 0 değerini döndürür. size() fonksiyonu, kuyruktaki eleman sayısını döndürür. Bu fonksiyon, kuyruğun eleman sayısını hesaplamak için kuyruğun başından sonuna tüm elemanları tarar.

Priority Queue (Öncelik Kuyruğu) Nedir?​

Priority Queue (Öncelik Kuyruğu), bir kuyruk yapısıdır ancak elemanlar öncelikli olarak sıralanır. Bu nedenle, normal bir kuyruktan farklı olarak, öncelik kuyruğundan çıkarılacak eleman, öncelik düzeyine göre seçilir. Yani, bir öncelik kuyruğunda, elemanlar önceliklerine göre düzenlenir ve öncelik seviyesi daha yüksek olan elemanlar, öncelik seviyesi daha düşük olan elemanlardan önce çıkarılır. Öncelik kuyrukları, birçok algoritma ve veri yapısında kullanılır, özellikle işlem önceliklerini yönetmek için kullanışlıdır. Öncelik kuyrukları, herhangi bir sıralama yöntemi kullanarak elemanların sıralanması ve öncelik seviyelerine göre elemanların işlenmesi için kullanılabilir.